#include "MySort.h"
#include <iostream>
using namespace std;

#define swap(a,b,t) { t=a; a=b; b=t; }

void CMySort::initData(int *Data)
{
	for(int i=0; i<m_iMax; i++)
		m_iData[i] = Data[i];
}

void CMySort::selectionSort()
{
	int temp;
	for(int last = m_iMax-1; last >= 1; --last){
		int largest = 0;
		for(int current = 1; current <= last; current++){
			if(m_iData[current] > m_iData[largest])
				largest = current;
		}
		swap(m_iData[largest], m_iData[last], temp);
	}
}

void CMySort::bubbleSort()
{
	int temp;
	bool bSorted = false;
	for(int pass = 1; (pass < m_iMax) && (!bSorted) ; pass++){
		bSorted = true;
		for(int current = 0; current < m_iMax-pass; current++){
			if(m_iData[current] > m_iData[current+1]){
				swap(m_iData[current], m_iData[current+1], temp);
				bSorted = false;
			}
		}
	}
}

void CMySort::shellSort()
{
	int i,j,h;
	int v;
	for(h=1; h<= m_iMax/9; h = 3*h+1);
	for(; h>0 ; h /= 3){
		for(i=h+1; i<m_iMax; i++){
			v = m_iData[i];
			j = i;
			while(j>=h && m_iData[j-h] > v){
				m_iData[j] = m_iData[j-h];
				j -= h;
			}
			m_iData[j] = v;
		}
	}
}

void CMySort::merge(int f, int m, int l)
{
	int *temp = new int[m_iMax];
	int first1 = f;
	int last1 = m;
	int first2 = m+1;
	int last2 = l;
	int index = first1;

	for(;first1 <= last1 && first2 <= last2; index++){
		if(m_iData[first1] < m_iData[first2]){
			temp[index] = m_iData[first1];
			first1++;
		}
		else{
			temp[index] = m_iData[first2];
			first2++;
		}
	}
	for(; first1 <= last1; first1++, index++)
		temp[index] = m_iData[first1];
	for(; first2 <= last2; first2++, index++)
		temp[index] = m_iData[first2];
	for(index = f; index <= l; index++)
		m_iData[index] = temp[index];
}

void CMySort::mergeSort(int f, int l)
{
	if(f<l){
		int middle = (f+l)/2;
		mergeSort(f,middle);
		mergeSort(middle+1,l);
		merge(f,middle,l);
	}
}

int CMySort::partition(int f, int l)
{
	int low, high;
	int p, t;
	p = m_iData[l];
	low = f-1;
	high = l;
	while(low < high){
		while(p > m_iData[++low]);
		while(p < m_iData[--high]);
		if(low < high){
			swap(m_iData[low], m_iData[high], t);
		}		
	}
	swap(m_iData[low], m_iData[l], t);
	return low;
}

void CMySort::quickSort(int f, int l)
{
	if(f < l){
		int pivotIndex = partition(f,l);
		quickSort(f, pivotIndex-1);
		quickSort(pivotIndex+1, l);
	}


}


void CMySort::printData()
{
	for(int i=0; i<m_iMax; i++)
		cout << m_iData[i] << " " ;
	cout << endl;
}